package com.test.demo;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * Created by jl on 2019/7/10 0010
 */
public class WordSplit2 {
    private static final HashSet<String> WORD_DIC = new HashSet<>();

    static {
        WORD_DIC.add("saying");
        WORD_DIC.add("friend");
        WORD_DIC.add("keep");
        WORD_DIC.add("you");
        WORD_DIC.add("i");
        WORD_DIC.add("are");
        WORD_DIC.add("my");
        WORD_DIC.add("good");
        WORD_DIC.add("no");
    }

    public static void main(String[] args) {
        String input = "ikeepsayingno";
        List<String> result = split(input);
        for (String a : result) {
            System.out.println(a);
        }
    }

    private static List<String> split(String input) {
        WordNode root = new WordNode(-1, "");
        doSplit(root, input);
        return filter(root, input);
    }

    private static List<String> filter(WordNode root, String orignStr) {
        List<String> result = new ArrayList<>();
        doFilter(result, root, "", orignStr);
        return result;
    }

    private static void doFilter(List<String> result, WordNode inputNode, String wordConcat, String orignStr) {
        String curConcat = wordConcat + " " + inputNode.word;
        if (isHitStrEnd(inputNode.word, inputNode.index, orignStr)) {
            result.add(curConcat.substring(2));
        }
        List<WordNode> nodes = inputNode.subWords;
        if (nodes == null) {
            return;
        }
        for (WordNode node : nodes) {
            doFilter(result, node, curConcat, orignStr);
        }
    }

    private static boolean isHitStrEnd(String curWord, int index, String orignStr) {
        return orignStr.length() == index + 1;
    }

    private static void doSplit(WordNode inputNode, String originStr) {
        char[] chars = originStr.substring(inputNode.index + 1).toCharArray();
        List<WordNode> wordNodes = new ArrayList<>();
        StringBuilder firstWordBuilder = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            firstWordBuilder.append(chars[i]);
            if (WORD_DIC.contains(firstWordBuilder.toString())) {
                wordNodes.add(new WordNode(i + inputNode.index + 1, firstWordBuilder.toString()));
            }
        }
        if (wordNodes.isEmpty()) {
            return;
        }
        inputNode.subWords = wordNodes;
        for (WordNode wordNode : wordNodes) {
            doSplit(wordNode, originStr);
        }
    }

    private static class WordNode {
        private int index;

        private String word;

        private List<WordNode> subWords;

        public WordNode(int index, String word) {
            this.index = index;
            this.word = word;
        }
    }
}
